<html><head><link href="../../../css-stylesheets/elucidator/program.css" rel="stylesheet" title="program" type="text/css" /> <title>Source file</title></head><body bgcolor="#ffffff" text="#000000" link="#000000" vlink="#000000"><font size="2"><pre><div class="schemedoc-abstract-comment">;;;; This is a Scheme library that support Finite State Automatons, both non-deterministic and deterministic.
;;;; The library includes a function that generates a deterministic automaton from a non-deterministic automaton.
;;;; Another central function is automaton-accepts? which accepts or rejects a list of input symbols in a DFA.
;;;; The generated automata are both compact and fast, because they make apply a rather efficient transition lookup in a sorted vector.
;;;; .title Reference Manual of the LAML Finite State Automaton library</div>
<span class="comment">; ---------------------------------------------------------------------------------------------------</span><br />
<div class="schemedoc-section-comment">;;; Automaton construction and selection.</div>
<a name="make-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Make a finite state automaton with a given start-state, a list of accept states, and a set of transitions - a list.
;; The optional parameter is a symbol map. In case it is passed, use this as symbol map for the resulting automaton,
;; and do not in this case compact the transitions. In normal use, do not pass any such symbol map. The function
;; make-finite-state-automaton will make the symbol map for you.
;; .form (make-finite-state-automaton start-state accept-state-list transitions [given-symbol-map])
;; .parameter start-state The start state of the automaton - an integer
;; .parameter accept-state-list The list of accepting states - a list of integers
;; .parameter transitions A list of transitions. Transitions are made by the function make-automaton-transition
;; .parameter given-symbol-map A symbol map - a sorted vector - ala an association list that maps real input symbols to terse symbols
;; .returns Returns a self-contained list structure that represents the finite state automaton.</div><a name="make-finite-state-automaton"></a><span><a href="../final-state-automaton.html#make-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(make-finite-state-automaton start-state accept-state-list transitions . optional-parameter-list)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">given-symbol-map</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#optional-parameter" title="Manual: general">optional-parameter</a> 1 optional-parameter-list #f)))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">automaton-alphabet</span> (<a class="applied-name" href="final-state-automaton-1.html#alphabet-of-automaton-transitions" title="final-state-automaton">alphabet-of-automaton-transitions</a> transitions))
	 (<span class="local-name-binding">symbol-map</span> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> given-symbol-map given-symbol-map (<a class="applied-name" href="final-state-automaton-1.html#make-automaton-symbol-map" title="final-state-automaton">make-automaton-symbol-map</a> automaton-alphabet)))
        )
    (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX332" title="R5RS Scheme form">list</a>
     'finite-state-automaton
     start-state
     accept-state-list
     (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX407" title="R5RS Scheme form">list-&gt;vector</a> (sort-list (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> given-symbol-map transitions (<a class="applied-name" href="final-state-automaton-1.html#compacted-transitions" title="final-state-automaton">compacted-transitions</a> transitions symbol-map)) <a class="applied-name" href="final-state-automaton-1.html#transition-leq?" title="final-state-automaton">transition-leq?</a>))
     symbol-map))))

<a name="start-state-of-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Return the start state of an automaton.
;; .form (start-state-of-finite-state-automaton aut)</div><a name="start-state-of-finite-state-automaton"></a><span><a href="../final-state-automaton.html#start-state-of-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">start-state-of-finite-state-automaton</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 2 "start-state-of-finite-state-automaton"))

<a name="final-states-of-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Return the list of final states of an automaton.
;; .form (final-states-of-finite-state-automaton aut)</div><a name="final-states-of-finite-state-automaton"></a><span><a href="../final-state-automaton.html#final-states-of-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">final-states-of-finite-state-automaton</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 3 "final-states-of-finite-state-automaton"))

<a name="transitions-of-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Return the transitions - a sorted vector - of an automaton.
;; .form (transitions-of-finite-state-automaton aut)</div><a name="transitions-of-finite-state-automaton"></a><span><a href="../final-state-automaton.html#transitions-of-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">transitions-of-finite-state-automaton</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 4 "transitions-of-finite-state-automaton"))

<a name="transition-list-of-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Return the transitions - as a list - of an automaton.</div><a name="transition-list-of-finite-state-automaton"></a><span><a href="../final-state-automaton.html#transition-list-of-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(transition-list-of-finite-state-automaton aut)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">trans-vec</span> (<a class="applied-name" href="final-state-automaton-1.html#transitions-of-finite-state-automaton" title="final-state-automaton">transitions-of-finite-state-automaton</a> aut)))
    (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX406" title="R5RS Scheme form">vector-&gt;list</a> trans-vec)))

<a name="symbol-map-of-finite-state-automaton"></a><div class="schemedoc-definition-comment">;; Return the symbol map of an automaton. The symbol is an internal device which maps real input symbol to
;; terse internal input symbols (for the sake of compact automaton representation).
;; .form (symbol-map-of-finite-state-automaton aut)</div><a name="symbol-map-of-finite-state-automaton"></a><span><a href="../final-state-automaton.html#symbol-map-of-finite-state-automaton"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">symbol-map-of-finite-state-automaton</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 5 "symbol-map-of-finite-state-automaton"))

<div class="schemedoc-section-comment">;;; State and transition predicates.</div>
<a name="state-equal?"></a><div class="schemedoc-definition-comment">;; The equality used for states in a finite state automaton. Normally, the states are integers.
;; .form (state-equal state1 state2).</div><a name="state-equal?"></a><span><a href="../final-state-automaton.html#state-equal?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">state-equal?</span> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a>)

<a name="state-leq?"></a><div class="schemedoc-definition-comment">;; A leq? function on states. The function is used to normalize subset states in the subset construction.
;; .form (state-leq? state1 state2)</div><a name="state-leq?"></a><span><a href="../final-state-automaton.html#state-leq?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">state-leq?</span> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX238" title="R5RS Scheme form">&lt;=</a>)

<a name="state-lt?"></a><div class="schemedoc-definition-comment">;; A less than function on states.
;; .form (state-lt state1 state2)</div><a name="state-lt?"></a><span><a href="../final-state-automaton.html#state-lt?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">state-lt?</span> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX236" title="R5RS Scheme form">&lt;</a>)

<a name="transition-leq?"></a><div class="schemedoc-definition-comment">;; A leq? function on transitions. The function is used for binary search among transitions for efficient lookup.</div><a name="transition-leq?"></a><span><a href="../final-state-automaton.html#transition-leq?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(transition-leq? trans1 trans2)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">from1</span> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans1))
       (<span class="local-name-binding">from2</span> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans2)))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="applied-name" href="final-state-automaton-1.html#state-lt?" title="final-state-automaton">state-lt?</a> from1 from2)
          #t)
        ((<a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a> from1 from2)
          (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">sym1</span> (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans1))
                (<span class="local-name-binding">sym2</span> (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans2)))
            (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> sym1) (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> sym2))
                     #t)
                  ((<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> sym1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> sym2)))
                      #t)
                  ((<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX346" title="R5RS Scheme form">symbol?</a> sym1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX346" title="R5RS Scheme form">symbol?</a> sym2))
                     (<a class="applied-name" href="final-state-automaton-1.html#symbol-leq?" title="final-state-automaton">symbol-leq?</a> sym1 sym2))
                  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">else</a> #f))))
        (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">else</a> #f))))

<a name="symbol-equal?"></a><div class="schemedoc-definition-comment">;; The equality used for symbols in a finite state automaton. Normally finite state automaton symbols are Scheme symbols.
;; .form (symbol-equal? sym1 sym2).</div><a name="symbol-equal?"></a><span><a href="../final-state-automaton.html#symbol-equal?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">symbol-equal?</span> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX199" title="R5RS Scheme form">eq?</a>)


<span class="comment">; ---------------------------------------------------------------------------------------------------</span><br /><div class="schemedoc-section-comment">;;; Transitions</div>
<a name="make-automaton-transition"></a><div class="schemedoc-definition-comment">;; Make a finite state transition</div><a name="make-automaton-transition"></a><span><a href="../final-state-automaton.html#make-automaton-transition"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(make-automaton-transition in-state symbol out-state)</span>
  (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX332" title="R5RS Scheme form">list</a> in-state symbol out-state))

<a name="from-state-of-transition"></a><div class="schemedoc-definition-comment">;; Return the from-state of the transition.
;; .form (from-state-of-transition trans)</div><a name="from-state-of-transition"></a><span><a href="../final-state-automaton.html#from-state-of-transition"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">from-state-of-transition</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 1 "from-state-of-transition"))

<a name="symbol-of-transition"></a><div class="schemedoc-definition-comment">;; Return the symbol of the transtion.
;; .form (symbol-of-transition trans)</div><a name="symbol-of-transition"></a><span><a href="../final-state-automaton.html#symbol-of-transition"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">symbol-of-transition</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 2 "symbol-of-transition"))

<a name="to-state-of-transition"></a><div class="schemedoc-definition-comment">;; Return the to-state of the transition.
;; .form (to-state-of-transition trans)</div><a name="to-state-of-transition"></a><span><a href="../final-state-automaton.html#to-state-of-transition"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">to-state-of-transition</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#make-selector-function" title="Manual: general">make-selector-function</a> 3 "to-state-of-transition"))

<a name="epsilon-symbol"></a><div class="schemedoc-definition-comment">;; The denotation for the empty symbol.</div><a name="epsilon-symbol"></a><span><a href="../final-state-automaton.html#epsilon-symbol"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">epsilon-symbol</span> #f)

<a name="epsilon-symbol?"></a><div class="schemedoc-definition-comment">;; Is the symbol s an epsilon symbol?</div><a name="epsilon-symbol?"></a><span><a href="../final-state-automaton.html#epsilon-symbol?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(epsilon-symbol? s)</span> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX305" title="R5RS Scheme form">boolean?</a> s) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> s)))

<a name="epsilon-transition?"></a><div class="schemedoc-definition-comment">;; Is the transition trans an epsilon transition?</div><a name="epsilon-transition?"></a><span><a href="../final-state-automaton.html#epsilon-transition?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(epsilon-transition? trans)</span> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans)))

<span class="comment">; ---------------------------------------------------------------------------------------------------
; TRANSITION MOVING</span><br />
<a name="last-automaton-input-symbol"></a><span class="comment">; The last tried automaton symbol input.
; Used for error message purposes.</span><br /><a name="last-automaton-input-symbol"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">last-automaton-input-symbol</span> #f)

<a name="automaton-input-number"></a><span class="comment">; The number of the input symbol just consumed</span><br /><a name="automaton-input-number"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">automaton-input-number</span> 0)


<a name="deterministic-automaton-move"></a><span class="comment">; Return a single state S for which there is a move M in automaton for which
; M(from-state, symbol) = S. If more than one such state exist, just return one of them.
; If no such move is possible, return #f.
; This function is designed to work well for deterministic automata.</span><br /><a name="deterministic-automaton-move"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(deterministic-automaton-move automaton from-state symbol)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">transitions</span> (<a class="applied-name" href="final-state-automaton-1.html#transitions-of-finite-state-automaton" title="final-state-automaton">transitions-of-finite-state-automaton</a> automaton))
        (<span class="local-name-binding">symbol-map</span> (<a class="applied-name" href="final-state-automaton-1.html#symbol-map-of-finite-state-automaton" title="final-state-automaton">symbol-map-of-finite-state-automaton</a> automaton))
        (<span class="local-name-binding">matching-transition</span> (<a class="applied-name" href="final-state-automaton-1.html#search-transitions" title="final-state-automaton">search-transitions</a> transitions from-state (<a class="applied-name" href="final-state-automaton-1.html#get-compact-automata-symbol" title="final-state-automaton">get-compact-automata-symbol</a> symbol symbol-map <a class="applied-name" href="final-state-automaton-1.html#unknown-symbol" title="final-state-automaton">unknown-symbol</a>))))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> <a class="applied-name" href="final-state-automaton-1.html#last-automaton-input-symbol" title="final-state-automaton">last-automaton-input-symbol</a> symbol)
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> <a class="applied-name" href="final-state-automaton-1.html#automaton-input-number" title="final-state-automaton">automaton-input-number</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX249" title="R5RS Scheme form">+</a> 1 <a class="applied-name" href="final-state-automaton-1.html#automaton-input-number" title="final-state-automaton">automaton-input-number</a>))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> matching-transition
      (<a class="applied-name" href="final-state-automaton-1.html#to-state-of-transition" title="final-state-automaton">to-state-of-transition</a> matching-transition)
      #f)))

<a name="deterministic-automaton-move*"></a><span class="comment">; Run the automaton a far as possible, deterministically, starting in state
; with symbol-list as input. Return the final state, or #f if the automaton goes dead without
; consuming all input.</span><br /><a name="deterministic-automaton-move*"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(deterministic-automaton-move* automaton state symbol-list)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> symbol-list) 
      state
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">next-state</span> (<a class="applied-name" href="final-state-automaton-1.html#deterministic-automaton-move" title="final-state-automaton">deterministic-automaton-move</a> automaton state (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> symbol-list))))
        (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> next-state
            (<a class="applied-name" href="final-state-automaton-1.html#deterministic-automaton-move*" title="final-state-automaton">deterministic-automaton-move*</a> automaton next-state (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> symbol-list))
            #f))))

<a name="trans-sel"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(trans-sel trans)</span>
  (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans) (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans)))

<a name="trans-eq?"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(trans-eq? cell1 cell2)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a>   (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell2)) <span class="comment">; in-states</span><br />       (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX199" title="R5RS Scheme form">eq?</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> cell1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> cell2)) <span class="comment">; symbols</span><br />  ))

<a name="trans-leq?"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(trans-leq? cell1 cell2)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX236" title="R5RS Scheme form">&lt;</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell2))
          #t)
        ((<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> cell2))
          (<a class="applied-name" href="final-state-automaton-1.html#symbol-leq?" title="final-state-automaton">symbol-leq?</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> cell1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> cell2)))
        (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">else</a> #f)))

<a name="search-transitions"></a><span class="comment">; Return a single transition among transitions that match from-state and symbol.
; If no such transition is found, return #f.
; transitions is a sorted vector of transitions</span><br /><a name="search-transitions"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(search-transitions transitions from-state symbol)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">search-res</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#binary-search-in-vector" title="Manual: general">binary-search-in-vector</a> transitions (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> from-state symbol) <a class="applied-name" href="final-state-automaton-1.html#trans-sel" title="final-state-automaton">trans-sel</a> <a class="applied-name" href="final-state-automaton-1.html#trans-eq?" title="final-state-automaton">trans-eq?</a> <a class="applied-name" href="final-state-automaton-1.html#trans-leq?" title="final-state-automaton">trans-leq?</a>)))
   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> search-res
       search-res         
       #f)))

<span class="comment">; ---------------------------------------------------------------------------------------------------------------</span><br />
<div class="schemedoc-section-comment">;;; Acceptance predicate.</div>
<a name="automaton-accepts?"></a><div class="schemedoc-definition-comment">;; Does automaton accepts the input symbol-list. 
;; This predicate should only be used if automaton is a DFA. If a NFA, first use the function subset-construction to construct a DFA from it.
;; This function outputs either #t of #f.</div><a name="automaton-accepts?"></a><span><a href="../final-state-automaton.html#automaton-accepts?"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(automaton-accepts? automaton symbol-list)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> <a class="applied-name" href="final-state-automaton-1.html#last-automaton-input-symbol" title="final-state-automaton">last-automaton-input-symbol</a> #f)
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> <a class="applied-name" href="final-state-automaton-1.html#automaton-input-number" title="final-state-automaton">automaton-input-number</a> 0)
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">end-state</span> 
        (<a class="applied-name" href="final-state-automaton-1.html#deterministic-automaton-move*" title="final-state-automaton">deterministic-automaton-move*</a> 
         automaton (<a class="applied-name" href="final-state-automaton-1.html#start-state-of-finite-state-automaton" title="final-state-automaton">start-state-of-finite-state-automaton</a> automaton) symbol-list)))
   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> end-state
       (<a class="schemedoc-name" href="../../../lib/man/general.html#turn-into-boolean" title="Manual: general">turn-into-boolean</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#member-by-predicate" title="Manual: general">member-by-predicate</a> end-state (<a class="applied-name" href="final-state-automaton-1.html#final-states-of-finite-state-automaton" title="final-state-automaton">final-states-of-finite-state-automaton</a> automaton) <a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a>))
       #f)))

   

<span class="comment">; ---------------------------------------------------------------------------------------------------</span><br />
<div class="schemedoc-section-comment">;;; DFA construction from NFA.
;;; Construction of deterministic finite automaton af non-deterministic finite state automaton.</div>
<a name="subset-construction"></a><div class="schemedoc-definition-comment">;; Return an equivalent DFA from the non-deterministic NFA passed as first parameter.
;; .form (subset-construction nfa [support-epsilon-moves?])
;; .parameter nfa A non-deterministic finite state automaton
;; .parameter support-epsilon-moves? A boolean parameter, defaulted to #f, which makes it possible to carry out the construction with epsilon moves in nfa</div><a name="subset-construction"></a><span><a href="../final-state-automaton.html#subset-construction"><img src="../../../images/elucidator/small-prev.gif" title="SchemeDoc Manual entry" alt="" border="0" /></a> <br /></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(subset-construction nfa . optional-parameter-list)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">support-epsilon-moves?</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#optional-parameter" title="Manual: general">optional-parameter</a> 1 optional-parameter-list #f)))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX123" title="R5RS Scheme form">letrec</a> ((<span class="local-name-binding">set-of-elements</span> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX332" title="R5RS Scheme form">list</a>))
    (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">input-symbols</span> 
            (<a class="schemedoc-name" href="../../../lib/man/general.html#remove-duplicates-by-predicate" title="Manual: general">remove-duplicates-by-predicate</a>
             (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">s</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> s))) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> <a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> (<a class="applied-name" href="final-state-automaton-1.html#transition-list-of-finite-state-automaton" title="final-state-automaton">transition-list-of-finite-state-automaton</a> nfa))) <a class="applied-name" href="final-state-automaton-1.html#symbol-equal?" title="final-state-automaton">symbol-equal?</a>))
	   (<span class="local-name-binding">dfa-start-state</span> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> support-epsilon-moves?
                                (<a class="applied-name" href="final-state-automaton-1.html#epsilon-closure-single-state" title="final-state-automaton">epsilon-closure-single-state</a> (<a class="applied-name" href="final-state-automaton-1.html#start-state-of-finite-state-automaton" title="final-state-automaton">start-state-of-finite-state-automaton</a> nfa) nfa)
                                (set-of-elements (<a class="applied-name" href="final-state-automaton-1.html#start-state-of-finite-state-automaton" title="final-state-automaton">start-state-of-finite-state-automaton</a> nfa))
                            ))
	   (<span class="local-name-binding">unmarked-dstates</span> (set-of-elements dfa-start-state))
	   (<span class="local-name-binding">dstates</span> (set-of-elements dfa-start-state)) <span class="comment">; a set of states, each a set (represented as a list).</span><br />	   (<span class="local-name-binding">dtrans</span> (set-of-elements))
	   )
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX128" title="R5RS Scheme form">do</a> ()
	  ((<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> unmarked-dstates) (<a class="applied-name" href="final-state-automaton-1.html#make-subset-dfa" title="final-state-automaton">make-subset-dfa</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX335" title="R5RS Scheme form">reverse</a> dstates) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX335" title="R5RS Scheme form">reverse</a> dtrans) nfa))
	(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">first-unmarked-dstate</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#first" title="Manual: general">first</a> unmarked-dstates)))
	  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> unmarked-dstates (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> unmarked-dstates))
	  (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX413" title="R5RS Scheme form">for-each</a> 
           (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">input-symbol</span>) 
             (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">u</span> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> support-epsilon-moves? 
                          (<a class="applied-name" href="final-state-automaton-1.html#epsilon-closure-set" title="final-state-automaton">epsilon-closure-set</a> (<a class="applied-name" href="final-state-automaton-1.html#subset-move" title="final-state-automaton">subset-move</a> nfa first-unmarked-dstate input-symbol) nfa)
                          (<a class="applied-name" href="final-state-automaton-1.html#subset-move" title="final-state-automaton">subset-move</a> nfa first-unmarked-dstate input-symbol))))
	       (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> u))
		   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX125" title="R5RS Scheme form">begin</a>
		     (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#member-by-predicate" title="Manual: general">member-by-predicate</a> u dstates <a class="applied-name" href="final-state-automaton-1.html#subset-state-equal?" title="final-state-automaton">subset-state-equal?</a>)) <span class="comment">; u is a set, dstates is a set of sets. </span><br />			 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX125" title="R5RS Scheme form">begin</a>
			   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> dstates (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> u dstates))
			   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> unmarked-dstates (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> u unmarked-dstates))))
		     (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">new-transition</span> 
			    (<a class="applied-name" href="final-state-automaton-1.html#make-automaton-transition" title="final-state-automaton">make-automaton-transition</a> first-unmarked-dstate input-symbol u)))
		       (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX106" title="R5RS Scheme form">set!</a> dtrans (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> new-transition dtrans)))))))  
           input-symbols)))))))

<a name="make-subset-dfa"></a><span class="comment">; Given states (in terms of nfa subset states), and transition-list (in terms of transitions between subset states),
; Return a (deterministic) finite state automaton with new equivalent numbered states.
; The start state of the automaton is the new state corresponding to (first states).
; The final states of the automaton are those states (subsets) that holds a final state in the nfa - properly transformed.</span><br /><a name="make-subset-dfa"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(make-subset-dfa states transition-list nfa)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">nfa-final-states</span> (<a class="applied-name" href="final-state-automaton-1.html#final-states-of-finite-state-automaton" title="final-state-automaton">final-states-of-finite-state-automaton</a> nfa))
        (<span class="local-name-binding">number-of-states</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX333" title="R5RS Scheme form">length</a> states))
        (<span class="local-name-binding">new-states</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#number-interval" title="Manual: general">number-interval</a> 0 (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX251" title="R5RS Scheme form">-</a> number-of-states 1)))
        (<span class="local-name-binding">old-new-state-map</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">old-state</span> <span class="local-name-binding">new-state</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> old-state new-state)) states new-states)))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX123" title="R5RS Scheme form">letrec</a> ((<span class="local-name-binding">old-to-new</span> 
            (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">old-state</span>)
              (<a class="applied-name" href="final-state-automaton-1.html#get-by-predicate" title="final-state-automaton">get-by-predicate</a> old-state old-new-state-map <a class="applied-name" href="final-state-automaton-1.html#subset-state-equal?" title="final-state-automaton">subset-state-equal?</a>))))
   (<a class="applied-name" href="final-state-automaton-1.html#make-finite-state-automaton" title="final-state-automaton">make-finite-state-automaton</a>
     (<a class="schemedoc-name" href="../../../lib/man/general.html#first" title="Manual: general">first</a> new-states)
     (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> old-to-new (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">old-state</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> (<a class="applied-name" href="final-state-automaton-1.html#intersection-by-predicate" title="final-state-automaton">intersection-by-predicate</a> old-state nfa-final-states <a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a>))))  states))
     (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> 
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">subset-transition</span>) 
        (<a class="applied-name" href="final-state-automaton-1.html#make-automaton-transition" title="final-state-automaton">make-automaton-transition</a> 
          (old-to-new (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> subset-transition))
          (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> subset-transition)
          (old-to-new (<a class="applied-name" href="final-state-automaton-1.html#to-state-of-transition" title="final-state-automaton">to-state-of-transition</a> subset-transition))))
      transition-list)
    (<a class="applied-name" href="final-state-automaton-1.html#symbol-map-of-finite-state-automaton" title="final-state-automaton">symbol-map-of-finite-state-automaton</a> nfa)
))))

<a name="epsilon-closure-single-state"></a><span class="comment">; Return the set of states in the nfa reachable from nfa-state by epsilon moves.
; (Not really needed for our purposes, but useful in general.)</span><br /><a name="epsilon-closure-single-state"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(epsilon-closure-single-state nfa-state nfa)</span>
  (<a class="applied-name" href="final-state-automaton-1.html#epsilon-closure-1" title="final-state-automaton">epsilon-closure-1</a> nfa-state nfa (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX332" title="R5RS Scheme form">list</a> nfa-state)))

<a name="epsilon-closure-set"></a><span class="comment">; Return the set of states in the nfa reachable from some nfa-state in nfa-state-set by epsilon moves.
; (Not really needed for our purposes, but useful in general.)</span><br /><a name="epsilon-closure-set"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(epsilon-closure-set nfa-state-set nfa)</span>
  (<a class="applied-name" href="final-state-automaton-1.html#state-subset-normalize" title="final-state-automaton">state-subset-normalize</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#flatten" title="Manual: general">flatten</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">nfa-state</span>) (<a class="applied-name" href="final-state-automaton-1.html#epsilon-closure-single-state" title="final-state-automaton">epsilon-closure-single-state</a> nfa-state nfa)) nfa-state-set))))

<a name="epsilon-closure-1"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(epsilon-closure-1 nfa-state nfa diregarded-end-states)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">relevant-transitions</span> 
         (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> 
          (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">trans</span>) (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans) nfa-state) (<a class="applied-name" href="final-state-automaton-1.html#epsilon-transition?" title="final-state-automaton">epsilon-transition?</a> trans))) 
          (<a class="applied-name" href="final-state-automaton-1.html#transition-list-of-finite-state-automaton" title="final-state-automaton">transition-list-of-finite-state-automaton</a> nfa)))
        (<span class="local-name-binding">end-states</span> (<a class="applied-name" href="final-state-automaton-1.html#state-subset-normalize" title="final-state-automaton">state-subset-normalize</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> <a class="applied-name" href="final-state-automaton-1.html#to-state-of-transition" title="final-state-automaton">to-state-of-transition</a> relevant-transitions)))
        (<span class="local-name-binding">end-states-filtered</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">dis-state</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#member-by-predicate" title="Manual: general">member-by-predicate</a> dis-state diregarded-end-states <a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a>))) end-states))
       )
  (<a class="applied-name" href="final-state-automaton-1.html#state-subset-normalize" title="final-state-automaton">state-subset-normalize</a>
   (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX334" title="R5RS Scheme form">append</a> 
     (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX332" title="R5RS Scheme form">list</a> nfa-state)
     end-states-filtered
     (<a class="schemedoc-name" href="../../../lib/man/general.html#flatten" title="Manual: general">flatten</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">state</span>) (<a class="applied-name" href="final-state-automaton-1.html#epsilon-closure-1" title="final-state-automaton">epsilon-closure-1</a> state nfa (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX334" title="R5RS Scheme form">append</a> diregarded-end-states end-states-filtered))) end-states-filtered)))
   )))
  

<a name="intersection-by-predicate"></a><span class="comment">; Return the list of those elements in lst which are also found in lst2. 
; Membership is measured by member-by-predicate</span><br /><a name="intersection-by-predicate"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(intersection-by-predicate lst1 lst2 pred)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> lst1) '())
        ((<a class="schemedoc-name" href="../../../lib/man/general.html#member-by-predicate" title="Manual: general">member-by-predicate</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> lst1) lst2 pred)
           (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> lst1) 
                 (<a class="applied-name" href="final-state-automaton-1.html#intersection-by-predicate" title="final-state-automaton">intersection-by-predicate</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> lst1) lst2 pred)))
        (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">else</a> (<a class="applied-name" href="final-state-automaton-1.html#intersection-by-predicate" title="final-state-automaton">intersection-by-predicate</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> lst1) lst2 pred))))

<a name="get-by-predicate"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(get-by-predicate key a-list pred)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">res</span> (<a class="applied-name" href="final-state-automaton-1.html#assq-by-predicate" title="final-state-automaton">assq-by-predicate</a> key a-list pred)))
   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX319" title="R5RS Scheme form">pair?</a> res) 
       (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> res)
       (error (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX392" title="R5RS Scheme form">string-append</a> "Get: Cannot find " (<a class="schemedoc-name" href="../../../lib/man/general.html#as-string" title="Manual: general">as-string</a> key) " in " (<a class="schemedoc-name" href="../../../lib/man/general.html#as-string" title="Manual: general">as-string</a> a-list))))))

<a name="assq-by-predicate"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(assq-by-predicate key a-list pred)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX330" title="R5RS Scheme form">null?</a> a-list) #f)
        ((pred key (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX325" title="R5RS Scheme form">caar</a> a-list)) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> a-list))
        (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">else</a> (<a class="applied-name" href="final-state-automaton-1.html#assq-by-predicate" title="final-state-automaton">assq-by-predicate</a> key (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> a-list) pred))))

<a name="subset-move"></a><span class="comment">; Aho, Sethi, Ullman page 118: move(T,a). nfa-state-set: T. symbol: a.</span><br /><a name="subset-move"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(subset-move nfa nfa-state-set symbol)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX122" title="R5RS Scheme form">let*</a> ((<span class="local-name-binding">nfa-transitions</span> (<a class="applied-name" href="final-state-automaton-1.html#transition-list-of-finite-state-automaton" title="final-state-automaton">transition-list-of-finite-state-automaton</a> nfa))
         (<span class="local-name-binding">relevant-transitions</span>
           (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> 
             (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">trans</span>) 
               (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#member-by-predicate" title="Manual: general">member-by-predicate</a> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans) nfa-state-set <a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a>)
                    (<a class="applied-name" href="final-state-automaton-1.html#symbol-equal?" title="final-state-automaton">symbol-equal?</a> symbol (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans))))
             nfa-transitions))
        )
    (<a class="applied-name" href="final-state-automaton-1.html#state-subset-normalize" title="final-state-automaton">state-subset-normalize</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> <a class="applied-name" href="final-state-automaton-1.html#to-state-of-transition" title="final-state-automaton">to-state-of-transition</a> relevant-transitions))))

<a name="state-subset-normalize"></a><span class="comment">; Sort states and remove duplicates</span><br /><a name="state-subset-normalize"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(state-subset-normalize state-subset)</span>
  (<a class="schemedoc-name" href="../../../lib/man/general.html#remove-duplicates-by-predicate" title="Manual: general">remove-duplicates-by-predicate</a> 
      (sort-list state-subset <a class="applied-name" href="final-state-automaton-1.html#state-leq?" title="final-state-automaton">state-leq?</a>)
      <a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a>))

<a name="subset-state-equal?"></a><span class="comment">; state-set1 and state-set1 are two sets of states, each represented as a list
; Is state-set1 and state-set2 considered equal?
; Assume that both state sets are normalized, meaning that the states in the list are sorted by state-leq?</span><br /><a name="subset-state-equal?"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(subset-state-equal? state-set1 state-set2)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX333" title="R5RS Scheme form">length</a> state-set1) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX333" title="R5RS Scheme form">length</a> state-set2))
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">eq-pairs</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">s1</span> <span class="local-name-binding">s2</span>) (<a class="applied-name" href="final-state-automaton-1.html#state-equal?" title="final-state-automaton">state-equal?</a> s1 s2))
                             state-set1 state-set2)))
         (<a class="schemedoc-name" href="../../../lib/man/general.html#accumulate-right" title="Manual: general">accumulate-right</a> <a class="applied-name" href="final-state-automaton-1.html#and-fn" title="final-state-automaton">and-fn</a> #t eq-pairs))
      #f))

<a name="and-fn"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(and-fn x y)</span> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> x y))

<span class="comment">; ---------------------------------------------------------------------------------------------------
; Unique symbols</span><br />
<a name="make-unique-symbol-list"></a><span class="comment">; Return a list of lgt unique symbols named systematically by the letters a .. z.
; Made via numbers in base 26 (the number of letters the English alphabet), using ciffers
; a..z, instead of 0..9a..z.</span><br /><a name="make-unique-symbol-list"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(make-unique-symbol-list lgt)</span>
  (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">n</span>) (<a class="schemedoc-name" href="../../../lib/man/general.html#as-symbol" title="Manual: general">as-symbol</a> (<a class="applied-name" href="final-state-automaton-1.html#special-number-in-base" title="final-state-automaton">special-number-in-base</a> n 26))) (<a class="schemedoc-name" href="../../../lib/man/general.html#number-interval" title="Manual: general">number-interval</a> 1 lgt)))


<a name="special-number-in-base"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(special-number-in-base n base)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a> n 0) "a"
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">ciffer-list</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX335" title="R5RS Scheme form">reverse</a> (<a class="applied-name" href="final-state-automaton-1.html#special-ciffers-in-base" title="final-state-automaton">special-ciffers-in-base</a> n base))))
     (<a class="applied-name" href="final-state-automaton-1.html#special-ciffer-output" title="final-state-automaton">special-ciffer-output</a> ciffer-list))))

<a name="special-ciffers-in-base"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(special-ciffers-in-base n base)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX235" title="R5RS Scheme form">=</a> n 0)
      '()
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">rem</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX260" title="R5RS Scheme form">modulo</a> n base))
            (<span class="local-name-binding">newn</span> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX258" title="R5RS Scheme form">quotient</a> n base)))
        (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> rem (<a class="applied-name" href="final-state-automaton-1.html#special-ciffers-in-base" title="final-state-automaton">special-ciffers-in-base</a> newn base)))))

<a name="special-ciffer-output"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(special-ciffer-output ciffer-list)</span>
 (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX411" title="R5RS Scheme form">apply</a> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX392" title="R5RS Scheme form">string-append</a>
    (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> <a class="applied-name" href="final-state-automaton-1.html#special-ciffer-translation" title="final-state-automaton">special-ciffer-translation</a> ciffer-list)))

<a name="special-ciffer-translation"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(special-ciffer-translation c)</span>
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX110" title="R5RS Scheme form">cond</a> ((<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX117" title="R5RS Scheme form">and</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX239" title="R5RS Scheme form">&gt;=</a> c 0) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX236" title="R5RS Scheme form">&lt;</a> c 26)) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX375" title="R5RS Scheme form">make-string</a> 1 (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX368" title="R5RS Scheme form">integer-&gt;char</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX249" title="R5RS Scheme form">+</a> c 97))))
        (t "?")))

<a name="unknown-symbol"></a><span class="comment">; A (presuably) never symbol never used in any automaton.</span><br /><a name="unknown-symbol"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">unknown-symbol</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#as-symbol" title="Manual: general">as-symbol</a> (<a class="applied-name" href="final-state-automaton-1.html#special-number-in-base" title="final-state-automaton">special-number-in-base</a> 100000 26)))


<span class="comment">; ---------------------------------------------------------------------------------------------------</span><br />
<a name="alphabet-of-automaton-transitions"></a><span class="comment">; Return the list of input symbols, as deduced from the automata transitions.</span><br /><a name="alphabet-of-automaton-transitions"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(alphabet-of-automaton-transitions transition-list)</span>
 (<a class="schemedoc-name" href="../../../lib/man/general.html#remove-duplicates-by-predicate" title="Manual: general">remove-duplicates-by-predicate</a>
  (<a class="schemedoc-name" href="../../../lib/man/general.html#filter" title="Manual: general">filter</a> 
    (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">s</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX304" title="R5RS Scheme form">not</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> s)))
    (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> <a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> transition-list)) <a class="applied-name" href="final-state-automaton-1.html#symbol-equal?" title="final-state-automaton">symbol-equal?</a>))

<a name="make-automaton-symbol-map"></a><span class="comment">; Return the automaton symbol map, which maps a real input symbol to a very short input symbol.
; The symbol map is a sorted vector, suitable for binary search.
; Both input and output is Scheme symbols.</span><br /><a name="make-automaton-symbol-map"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(make-automaton-symbol-map alphabet-symbols)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">unique-symbol-list</span> (<a class="applied-name" href="final-state-automaton-1.html#make-unique-symbol-list" title="final-state-automaton">make-unique-symbol-list</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX333" title="R5RS Scheme form">length</a> alphabet-symbols))))
  (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX407" title="R5RS Scheme form">list-&gt;vector</a>
   (sort-list 
     (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">s</span> <span class="local-name-binding">us</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX320" title="R5RS Scheme form">cons</a> s us)) alphabet-symbols unique-symbol-list)
     (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">pair1</span> <span class="local-name-binding">pair2</span>) (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX385" title="R5RS Scheme form">string&lt;=?</a> (<a class="schemedoc-name" href="../../../lib/man/general.html#as-string" title="Manual: general">as-string</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> pair1)) (<a class="schemedoc-name" href="../../../lib/man/general.html#as-string" title="Manual: general">as-string</a> (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> pair2))))))))

<a name="compacted-transitions"></a><span class="comment">; Transform transitions (a list of transitions) such that the ordinary symbols are replaced by the compact symbols,
; which are the target symbols symbol-map</span><br /><a name="compacted-transitions"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(compacted-transitions transitions symbol-map)</span>
 (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX412" title="R5RS Scheme form">map</a> 
   (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX98" title="R5RS Scheme form">lambda</a> (<span class="local-name-binding">trans</span>) 
    (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">fr</span> (<a class="applied-name" href="final-state-automaton-1.html#from-state-of-transition" title="final-state-automaton">from-state-of-transition</a> trans))
          (<span class="local-name-binding">sy</span> (<a class="applied-name" href="final-state-automaton-1.html#symbol-of-transition" title="final-state-automaton">symbol-of-transition</a> trans))
          (<span class="local-name-binding">to</span> (<a class="applied-name" href="final-state-automaton-1.html#to-state-of-transition" title="final-state-automaton">to-state-of-transition</a> trans)))
      (<a class="applied-name" href="final-state-automaton-1.html#make-automaton-transition" title="final-state-automaton">make-automaton-transition</a> fr (<a class="applied-name" href="final-state-automaton-1.html#get-compact-automata-symbol" title="final-state-automaton">get-compact-automata-symbol</a> sy symbol-map) to)))
   transitions))

<a name="symbol-leq?"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(symbol-leq? s1 s2)</span>
 (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX385" title="R5RS Scheme form">string&lt;=?</a> (symbol->string s1) (symbol->string s2)))

<a name="problem-map"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">problem-map</span> #f)

<a name="get-compact-automata-symbol"></a><span></span>(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_7.html#IDX173" title="R5RS Scheme form">define</a> <span class="signature">(get-compact-automata-symbol sy symbol-map . optional-parameter-list)</span>
 (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">default-result</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#optional-parameter" title="Manual: general">optional-parameter</a> 1 optional-parameter-list #f)))
  (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> (<a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol?" title="final-state-automaton">epsilon-symbol?</a> sy)
      <a class="applied-name" href="final-state-automaton-1.html#epsilon-symbol" title="final-state-automaton">epsilon-symbol</a>
      (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX121" title="R5RS Scheme form">let</a> ((<span class="local-name-binding">search-res</span> (<a class="schemedoc-name" href="../../../lib/man/general.html#binary-search-in-vector" title="Manual: general">binary-search-in-vector</a> symbol-map sy <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX321" title="R5RS Scheme form">car</a> <a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX199" title="R5RS Scheme form">eq?</a> <a class="applied-name" href="final-state-automaton-1.html#symbol-leq?" title="final-state-automaton">symbol-leq?</a>)))
	(<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> search-res
	    (<a class="scheme-procedure-name" href="../../../r5rs/r5rs_8.html#IDX322" title="R5RS Scheme form">cdr</a> search-res)
	    (<a class="scheme-syntax-name" href="../../../r5rs/r5rs_6.html#IDX103" title="R5RS Scheme form">if</a> default-result
	        default-result
	        (<a class="schemedoc-name" href="../../../lib/man/general.html#laml-error" title="Manual: general">laml-error</a> "get-compact-automata-symbol: Cannot find value of symbol" sy "in" symbol-map)))))))





</pre></font><div>&nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p> &nbsp; <p></p></div></body></html>